//==============================================================================
// Copyright (c) 2008-2013 Niall Ryan. All Rights Reserved.
//==============================================================================

#ifndef HYDRA_HASHMAPS_LOCKFREEVECTOR_H
#define HYDRA_HASHMAPS_LOCKFREEVECTOR_H 1

#include "hydra/allocators/BasicAllocator.h"
#include "hydra/atomic/Atomic.h"

namespace Hydra
{
	/**
	 * Lock-free vector, indexed access and dynamically resizable.
	 */
	template<typename T, typename Allocator=BasicAllocator, unsigned int INITIAL_CAPACITY_LOG=5,
		unsigned int MAX_CAPACITY_LOG=32>
	class LockFreeVector
	{
	public:
		LockFreeVector();
		~LockFreeVector();

		const T& operator[](unsigned int i) const;
		T& operator[](unsigned int i);

		void pushBack(const T& v);

		bool isEmpty() const         { return (m_size == 0); }
		unsigned int getSize() const { return m_size; }

		void clear();
		void resize(unsigned int newSize);
		void compareAndSwapSize(unsigned int oldSize, unsigned int newSize);

	private:
		unsigned int getChunkForIndex(unsigned int index) const;
		unsigned int getChunkSize(unsigned int chunkIndex) const;
		T* getChunk(unsigned int chunkIndex);
		T* allocateChunk(unsigned int chunkIndex);

		static const unsigned int MAX_NUM_CHUNKS = MAX_CAPACITY_LOG-(INITIAL_CAPACITY_LOG-1);
		Atomic<T*> m_chunks[MAX_NUM_CHUNKS];

		Atomic<unsigned int> m_size;
		Allocator m_alloc;
	};

	//==================================================================================================
	//==================================================================================================
	//==================================================================================================

	template<typename T, typename Allocator, unsigned int INITIAL_CAPACITY_LOG, unsigned int MAX_CAPACITY_LOG>
	inline LockFreeVector<T, Allocator, INITIAL_CAPACITY_LOG, MAX_CAPACITY_LOG>::LockFreeVector()
	{
		m_size = 0;
		for( int i=0; i<MAX_NUM_CHUNKS; ++i )
			m_chunks[i] = NULL;
	}

	template<typename T, typename Allocator, unsigned int INITIAL_CAPACITY_LOG, unsigned int MAX_CAPACITY_LOG>
	inline LockFreeVector<T, Allocator, INITIAL_CAPACITY_LOG, MAX_CAPACITY_LOG>::~LockFreeVector()
	{
		for( int i=0; i<MAX_NUM_CHUNKS; ++i )
		{
			if( m_chunks[i] )
				m_alloc.free(m_chunks[i]);
		}
	}

	template<typename T, typename Allocator, unsigned int INITIAL_CAPACITY_LOG, unsigned int MAX_CAPACITY_LOG>
	inline unsigned int LockFreeVector<T, Allocator, INITIAL_CAPACITY_LOG, MAX_CAPACITY_LOG>::getChunkForIndex(
		unsigned int index) const
	{
		//find highest set bit in the bucket index
		unsigned int highestBitSet = INITIAL_CAPACITY_LOG-1;
		unsigned int v = index >> INITIAL_CAPACITY_LOG;
		while( v )
		{
			++highestBitSet;
			v >>= 1;
		}
		
		unsigned int chunkIndex = highestBitSet - (INITIAL_CAPACITY_LOG-1);
		assert(chunkIndex<MAX_NUM_CHUNKS);
		return chunkIndex;
	}

	template<typename T, typename Allocator, unsigned int INITIAL_CAPACITY_LOG, unsigned int MAX_CAPACITY_LOG>
	inline unsigned int LockFreeVector<T, Allocator, INITIAL_CAPACITY_LOG, MAX_CAPACITY_LOG>::getChunkSize(
		unsigned int chunkIndex) const
	{
		//each chunk is double the size of the previous one
		//first chunk is an exception, it is twice as big because it contains storage for the missing small chunks too
		if( chunkIndex == 0 )
			return 1 << INITIAL_CAPACITY_LOG;
		else
			return 1 << (chunkIndex+INITIAL_CAPACITY_LOG-1);
	}

	template<typename T, typename Allocator, unsigned int INITIAL_CAPACITY_LOG, unsigned int MAX_CAPACITY_LOG>
	inline T* LockFreeVector<T, Allocator, INITIAL_CAPACITY_LOG, MAX_CAPACITY_LOG>::getChunk(unsigned int chunkIndex)
	{
		T* chunk = m_chunks[chunkIndex];
		if( !chunk )
		{
			return allocateChunk(chunkIndex);
		}
		return chunk;
	}

	template<typename T, typename Allocator, unsigned int INITIAL_CAPACITY_LOG, unsigned int MAX_CAPACITY_LOG>
	inline T* LockFreeVector<T, Allocator, INITIAL_CAPACITY_LOG, MAX_CAPACITY_LOG>::allocateChunk(
		unsigned int chunkIndex)
	{
		//allocate a new chunk, and attempt to assign it atomically with a compareAndSwap
		unsigned int chunkSize = getChunkSize(chunkIndex);
		T* newChunk = static_cast<T*>(m_alloc.alloc(chunkSize*sizeof(T)));
		//zero initialize memory, useful for LockFreeHashMap in particular, but perhaps should be a policy?
		memset(newChunk, 0, chunkSize*sizeof(T));
		T* oldChunk = m_chunks[chunkIndex].compareAndSwap(newChunk, NULL);
		if( oldChunk )
		{
			//somebody beat us to it, that's ok, use their chunk and free our attempted allocation
			m_alloc.free(newChunk);
			return oldChunk;
		}
		return newChunk;
	}

	template<typename T, typename Allocator, unsigned int INITIAL_CAPACITY_LOG, unsigned int MAX_CAPACITY_LOG>
	inline T& LockFreeVector<T, Allocator, INITIAL_CAPACITY_LOG, MAX_CAPACITY_LOG>::operator[](unsigned int i)
	{
		assert(i<m_size);
		unsigned int chunkIndex = getChunkForIndex(i);
		unsigned int chunkSize = getChunkSize(chunkIndex);
		T* chunk = getChunk(chunkIndex);
		return chunk[i & (chunkSize-1)];
	}

	template<typename T, typename Allocator, unsigned int INITIAL_CAPACITY_LOG, unsigned int MAX_CAPACITY_LOG>
	inline const T& LockFreeVector<T, Allocator, INITIAL_CAPACITY_LOG, MAX_CAPACITY_LOG>::operator[](
		unsigned int i) const
	{
		return (*const_cast<LockFreeVector<T, Allocator>*>(this))[i];
	}

	template<typename T, typename Allocator, unsigned int INITIAL_CAPACITY_LOG, unsigned int MAX_CAPACITY_LOG>
	inline void LockFreeVector<T, Allocator, INITIAL_CAPACITY_LOG, MAX_CAPACITY_LOG>::pushBack(const T& v)
	{
		unsigned int index = m_size.getAndIncrement();
		(*this)[index] = v;
	}

	template<typename T, typename Allocator, unsigned int INITIAL_CAPACITY_LOG, unsigned int MAX_CAPACITY_LOG>
	inline void LockFreeVector<T, Allocator, INITIAL_CAPACITY_LOG, MAX_CAPACITY_LOG>::clear()
	{
		m_size = 0;
	}

	template<typename T, typename Allocator, unsigned int INITIAL_CAPACITY_LOG, unsigned int MAX_CAPACITY_LOG>
	inline void LockFreeVector<T, Allocator, INITIAL_CAPACITY_LOG, MAX_CAPACITY_LOG>::resize(unsigned int newSize)
	{
		m_size = newSize;
	}

	template<typename T, typename Allocator, unsigned int INITIAL_CAPACITY_LOG, unsigned int MAX_CAPACITY_LOG>
	inline void LockFreeVector<T, Allocator, INITIAL_CAPACITY_LOG, MAX_CAPACITY_LOG>::compareAndSwapSize(
		unsigned int oldSize, unsigned int newSize)
	{
		m_size.compareAndSwap(newSize, oldSize);
	}
}

#endif
